Reading � Kenny�s overview of Hofstadter on Godel

Greg Detre

Wednesday, 10 April, 2002

see: �C:\greg\academic\reading\phil\topics\mind\Hofstadter's stuff on Godel and Godel's Theorem Math.htm�

Introduction

The idea was that this system would represent every statement you could possibly make about natural numbers. So if you made the statement "every even number greater than two is the sum of two primes," you would be able to prove strictly and mechanically, from the axioms, that it is either true or false. For real, die-hard mathematicians, the words "true" and "false" would become shorthand for "provable" or "disprovable" within the system

G� showed that for any formal axiomatic system, there is always a statement about natural numbers which is true, but which cannot be proven in the system

A road map of where we�re about to go

It simply assumes that TNT is perfect, and proceeds from there to a paradox. In doing so, it crushes any system which makes similar claims of perfection

Typographical number theory (TNT)

axioms etc.

xxx

The Awesome Power of TNT

being a TNT proponent means holding the following two statements to be true:

TNT expresses number theory

1. Any statement you can make about natural numbers�no matter how complex, no matter how long, no matter how bizarre�can be written in a TNT string.

TNT represents number theory

2. If such a statement is true, its TNT string can be derived as a theorem from the axioms. If the statement is false, we can derive its converse from the axioms. (Meaning, the same string with a ~ symbol in front of it.)

this is equivalent to assuming that TNT succeeds in its lofty goal of symbolically representing all of number theory in a cohesive system

based on this assumption, we are going to lead ourselves to an inevitable contradiction, and thus prove we were wrong to assume that any system could make these claims.

G�'s Theorem: The Very End of the Proof

The critical step is to take the following statement, which Hofstadter calls "sentence G," and translate it into a TNT-string.

Sentence G: This statement is not a theorem of TNT.

Now, ask yourself this question: is sentence G true or false?

If sentence G is false, then it is a theorem of TNT. Then we have a valid theorem which is false, and the whole system falls apart.

So it must be true. But if it is true, then it is not a theorem of TNT. Which means that sentence G is true, but it is not provable within TNT. That is G�'s "incompleteness." He showed that TNT, although it may be perfectly consistent and always correct, cannot possibly prove every true statement about number theory; there is always something which is true, which the system cannot prove. So we're done!

but TNT makes statements about numbers, and sentence G is a statement about a statement (itself). So while writing a TNT-string for "100 is a power of 10" might be very difficult, it seems reasonable to grant that it's possible; but translating sentence G into TNT seems about as likely as yodeling in sign language

to recap:

First, if we could translate sentence G into TNT, we would have defeated TNT. Second, there is no way to translate sentence G into TNT as we have formulated it. Once both of those seem obvious, you will be ready for what is probably the most brilliant part of G�'s proof, which is that he found a way to talk about statements in a language that was only meant to discuss numbers.

A slight change in notation

We aren't going to change the axioms. We aren't going to change the rules. We're just going to change the symbols.

replace each symbol with an arbitrary, unique three-digit number

nothing has changed. If TNT was valid, the G�ized version is exactly as valid

in our new notation, every string is a number. Because of this, we can change the form of our rules, from typographical manipulations to mathematical functions

e.g.

Fake rule: Whenever a string ends in the symbol "000", you can replace that symbol with "005".

The same fake rule, written differently: Whenever a number is a multiple of 1000, you can add 5 to it.

Our original TNT strings were interpreted as being "strings about numbers." That was a very familiar idea: after all, we all learned in first grade to treat "1+1=2" as a string about numbers! But in the G�ized version, we have something slightly different: numbers about numbers. In this system, the number 123666112666111123666 means "1+0=1"; and the number 123666111666 means "1=0".

Godel�s proof required us to write a TNT string about a TNT string; and we said that was impossible, because TNT strings are only about numbers

G� notation is a step in the right direction, since it blurs the distinction between numbers and statements

One good clarification technique is to note that we have three different ways now of talking about exactly the same information: number theory, TNT, and G�-numbered TNT. All three systems have axioms, and rules of production for turning those axioms into theorems; but these elements look very different in the different systems. I've tried to summarize the entire thing in the following chart.

Mathematical Logic	TNT	G�-numbered TNT
An axiom is an "obvious" statement about natural numbers.	An axiom is a statement string	An axiom is a number
A rule of production is a logical way to work with axioms.	A rule of production is an allowed string-manipulation mechanism.	A rule of production is an allowed mathematical function.
The theorems you produce are new statements about natural numbers.	The theorems you produce are new strings.	The theorems you produce are new numbers.

Definition: A number has theoremhood if it corresponds to a valid theorem of TNT�or, in other words, to a true statement about numbers.

However, I prefer the following definition.

Alternative definition: A number has theoremhood if it is possible to create that number from our small set of axiom-numbers, by the application of our small set of function-rules.

I'm going to start off with a true fact, and write it three different ways: in terms of maths, in terms of TNT, and in terms of G�ized TNT.

"Zero equals zero" is true.
The string 0=0 is a valid TNT theorem (ie can be derived from axioms).
The number 666111666 has the theoremhood property.

Now, I want to focus on sentence 3. I mentioned earlier that "theoremhood" is just a mathematical concept, like "primeness" or "squareness." In fact, we could rewrite this sentence as "It is possible to take certain numbers, apply certain functions to them, and arrive at 666111666."

Now, once again, remember that we are assuming TNT can express any mathematical statement, no matter how complex. So presumably it can handle this one: we could take the sentence "666111666 has theoremhood," and translate it into TNT!

The resulting string would presumably be true, leading us to the following claim, which I will again write in three equivalent ways.

"666111666 has theoremhood" is true.
The TNT string for "666111666 has theoremhood" is a valid TNT theorem.
The G� number for the TNT string for "666111666 has theoremhood," has theoremhood.

If we want, we can start spiralling up forever at this point. This sentence 3 is a new mathematical statement, and could be the "1" of another triad: we could translate it into TNT, G�ize that string, claim theoremhood for our new number, and so on.

the point is: it is possible to write a TNT string which says that another TNT string is (or is not) a valid theorem

I simply asserted that it is possible to translate that string, because that string is a mathematical statement, and we are assuming that TNT can express all mathematical statements.

But G is Still Harder to Write Than it Looks

At this point, you may well think we're done. We have shown that sentence G destroys TNT's claim to completely represent natural numbers. All we have to do is show that sentence G can, in fact, be translated into TNT. And we've done the hard part there, which is showing that "TNT Theoremhood" is a mathematical concept that can be expressed in TNT. So we know that the following sentences could all be written in TNT.

All we need to do is find such a sentence with the following peculiarity: the number that it talks about, happens to be the G� number of the sentence itself. Is that so hard?

Actually, it�s impossible: the G� number for any number is much bigger than the number itself

Sentence G has to have some very clever, indirect reference to its own G� number

"Arithmoquining" to Get TNT Sentences About TNT Sentences

My summary

we�re proposing that everything you could want to say (represent + express) about natural numbers could be boiled down to a formal language that consists of a few starting axioms, and the rules to manipulate them (preserving truth) into theorems

if we just take this formal language and use arbitrary, unique 3-digit numbers as symbols, and arithmetical rather than typographical manipulations, then theoremhood becomes just another property of numbers (like primeness of squareness), and so can be expressed in TNT, e.g. �the number 123666123etc. has the property of theoremhood�, where that number is a Godelized TNT theorem that says �???

sentence G: this �???

all you have to do then is Godelize the TNT theorem that means �this number � ???

Questions

how do we know that TNT is about numbers??? how do we know that a true TNT theorem will apply to number theory???

i think a 'true theorem' is a tautology, cos any theorem derived f the axioms is assumed to be true... (and similarly, falsity is a theorem with logical NOT in front that can be derived from the axioms)

�So [sentence G] must be true. But if it is true, then it is not a theorem of TNT. Which means that sentence G is true, but it is not provable within TNT. That is G�'s "incompleteness." He showed that TNT, although it may be perfectly consistent and always correct, cannot possibly prove every true statement about number theory; there is always something which is true, which the system cannot prove. So we're done!� � why does this show incompleteness???